// Hxt - Copyright (C) 
// 2016 - 2020 UCLouvain
//
// See the LICENSE.txt file for license information.
//
// Contributor(s):
//   Célestin Marot

#include "hxt_omp.h"
#include "hxt_vertices.h"
#include "hxt_sort.h"
#include <string.h>


#if defined( __BMI2__ ) || defined( __AVX2__ ) || (defined(__AVX512F__) && defined(__AVX512VL__))
#include <immintrin.h>
#endif

/**
* \file hxt_vertices.c see header hxt_vertices.h.
* \author Célestin Marot
*/

/* create a nextbefore macro
 * for a strictly positive value, round to previous double value */
#if (defined (__STD_VERSION__) && (__STD_VERSION__ >= 199901L)) \
 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) // nextafter only from C99
#include <math.h>
static inline double nextbeforef(double x) {
  return nextafter(x,0.0);
}
#else
static inline double nextbeforef(double x) {
  union {double f; int64_t d; } v = {x};
  v.d--;
  return v.f;
}
#endif

// fill zorder and return first 3 bits
static inline uint64_t Zorder(uint32_t xyz[]) {
#ifndef __BMI2__
  static const uint64_t hxtDeclareAligned morton7[128] =
  {
0x00000,0x00001,0x00008,0x00009,0x00040,0x00041,0x00048,0x00049, 
0x00200,0x00201,0x00208,0x00209,0x00240,0x00241,0x00248,0x00249, 
0x01000,0x01001,0x01008,0x01009,0x01040,0x01041,0x01048,0x01049, 
0x01200,0x01201,0x01208,0x01209,0x01240,0x01241,0x01248,0x01249, 
0x08000,0x08001,0x08008,0x08009,0x08040,0x08041,0x08048,0x08049, 
0x08200,0x08201,0x08208,0x08209,0x08240,0x08241,0x08248,0x08249, 
0x09000,0x09001,0x09008,0x09009,0x09040,0x09041,0x09048,0x09049, 
0x09200,0x09201,0x09208,0x09209,0x09240,0x09241,0x09248,0x09249, 
0x40000,0x40001,0x40008,0x40009,0x40040,0x40041,0x40048,0x40049, 
0x40200,0x40201,0x40208,0x40209,0x40240,0x40241,0x40248,0x40249, 
0x41000,0x41001,0x41008,0x41009,0x41040,0x41041,0x41048,0x41049, 
0x41200,0x41201,0x41208,0x41209,0x41240,0x41241,0x41248,0x41249, 
0x48000,0x48001,0x48008,0x48009,0x48040,0x48041,0x48048,0x48049, 
0x48200,0x48201,0x48208,0x48209,0x48240,0x48241,0x48248,0x48249, 
0x49000,0x49001,0x49008,0x49009,0x49040,0x49041,0x49048,0x49049, 
0x49200,0x49201,0x49208,0x49209,0x49240,0x49241,0x49248,0x49249
  };

  return morton7[xyz[0] & 0x7F] |
         morton7[xyz[1] & 0x7F]<<1 |
         morton7[xyz[2] & 0x7F]<<2 |
         (uint64_t) morton7[xyz[0]>>7 & 0x7F]<<21 |
         (uint64_t) morton7[xyz[1]>>7 & 0x7F]<<22 |
         (uint64_t) morton7[xyz[2]>>7 & 0x7F]<<23 |
         (uint64_t) morton7[xyz[0]>>14 & 0x7F]<<42 |
         (uint64_t) morton7[xyz[1]>>14 & 0x7F]<<43 |
         (uint64_t) morton7[xyz[2]>>14 & 0x7F]<<44;
#else
  return _pdep_u64(xyz[0], UINT64_C(0x1249249249249249)) |
         _pdep_u64(xyz[1], UINT64_C(0x2492492492492492)) | 
         _pdep_u64(xyz[2], UINT64_C(0x4924924924924924));
#endif
}


/*================================= compute the hilberts distance ===========================================
 *
 * This part is for computing the hilbert coordinates of the vertices (X,Y,Z)
 * shift[i] must be between 0 and 1
 */
// TODO: special function for AVX512: it can be super optimized !!! :-)
HXTStatus hxtMoore(HXTBbox* bbox, HXTVertex* vertices, const uint32_t n, const double* mid01)
{
HXT_ASSERT(vertices!=NULL);
HXT_ASSERT(bbox!=NULL);
HXT_ASSERT_MSG(bbox->min[0]<bbox->max[0] ||
               bbox->min[1]<bbox->max[1] ||
               bbox->min[2]<bbox->max[2],"wrong bounding box");

  static const uint16_t hxtDeclareAligned moore_hilbert2[512] = {
// The only Ca coordinate-shifting Moore at first iter and Ca00.c4I (aka Butz) at 2 other iter
5684,4663,5683,1584,565,566,5170,5169,1080,4159,57,4670,2107,2108,58,4669,5676,4655,5675,1576,557,558,5162,5161,4644,1061,5159,1062,4643,5666,2080,5665,3594,3593,2061,2062,1035,4616,1036,1551,5124,5123,5,4610,5639,2560,6,4609,3602,3601,2069,2070,1043,4624,1044,1559,4636,1053,5151,1054,4635,5658,2072,5657,576,1089,1603,1090,3655,5702,1604,5701,3674,3673,2141,2142,1115,4696,1116,1631,4732,1149,5247,1150,4731,5754,2168,5753,3682,3681,2149,2150,1123,4704,1124,1639,1096,4175,73,4686,2123,2124,74,4685,1104,4183,81,4694,2131,2132,82,4693,3190,1649,1143,4208,3189,1650,3700,3699,3182,1641,1135,4200,3181,1642,3692,3691,5844,4823,5843,1744,725,726,5330,5329,728,1241,1755,1242,3807,5854,1756,5853,5836,4815,5835,1736,717,718,5322,5321,3270,1729,1223,4288,3269,1730,3780,3779,3818,3817,2285,2286,1259,4840,1260,1775,736,1249,1763,1250,3815,5862,1764,5861,3826,3825,2293,2294,1267,4848,1268,1783,3322,1789,763,764,3321,1790,5880,2815,640,1153,1667,1154,3719,5766,1668,5765,3738,3737,2205,2206,1179,4760,1180,1695,4796,1213,5311,1214,4795,5818,2232,5817,3746,3745,2213,2214,1187,4768,1188,1703,1160,4239,137,4750,2187,2188,138,4749,1168,4247,145,4758,2195,2196,146,4757,3254,1713,1207,4272,3253,1714,3764,3763,3246,1705,1199,4264,3245,1706,3756,3755,6132,5111,6131,2032,1013,1014,5618,5617,1528,4607,505,5118,2555,2556,506,5117,6124,5103,6123,2024,1005,1006,5610,5609,5092,1509,5607,1510,5091,6114,2528,6113,4042,4041,2509,2510,1483,5064,1484,1999,5572,5571,453,5058,6087,3008,454,5057,4050,4049,2517,2518,1491,5072,1492,2007,5084,1501,5599,1502,5083,6106,2520,6105,5556,5555,437,5042,6071,2992,438,5041,5548,5547,429,5034,6063,2984,430,5033,3466,1933,907,908,3465,1934,6024,2959,3474,1941,915,916,3473,1942,6032,2967,952,1465,1979,1466,4031,6078,1980,6077,6052,5031,6051,1952,933,934,5538,5537,4996,1413,5511,1414,4995,6018,2432,6017,6044,5023,6043,1944,925,926,5530,5529,5908,4887,5907,1808,789,790,5394,5393,792,1305,1819,1306,3871,5918,1820,5917,5900,4879,5899,1800,781,782,5386,5385,3334,1793,1287,4352,3333,1794,3844,3843,3882,3881,2349,2350,1323,4904,1324,1839,800,1313,1827,1314,3879,5926,1828,5925,3890,3889,2357,2358,1331,4912,1332,1847,3386,1853,827,828,3385,1854,5944,2879,5492,5491,373,4978,6007,2928,374,4977,5484,5483,365,4970,5999,2920,366,4969,3402,1869,843,844,3401,1870,5960,2895,3410,1877,851,852,3409,1878,5968,2903,888,1401,1915,1402,3967,6014,1916,6013,5988,4967,5987,1888,869,870,5474,5473,4932,1349,5447,1350,4931,5954,2368,5953,5980,4959,5979,1880,861,862,5466,5465
  };


  static const uint16_t hxtDeclareAligned hilbert3[6144] = {
// Ca00.c4I aka Butz
0,2563,3079,2564,513,514,5126,5125,5692,4671,5691,1592,573,574,5178,5177,520,1033,1547,1034,3599,5646,1548,5645,4150,567,4149,3124,2609,3632,2610,3123,3098,1565,539,540,3097,1566,5656,2591,3106,1573,547,548,3105,1574,5664,2599,528,1041,1555,1042,3607,5654,1556,5653,4142,559,4141,3116,2601,3624,2602,3115,576,1089,1603,1090,3655,5702,1604,5701,3674,3673,2141,2142,1115,4696,1116,1631,4732,1149,5247,1150,4731,5754,2168,5753,3682,3681,2149,2150,1123,4704,1124,1639,1096,4175,73,4686,2123,2124,74,4685,1104,4183,81,4694,2131,2132,82,4693,3190,1649,1143,4208,3189,1650,3700,3699,3182,1641,1135,4200,3181,1642,3692,3691,5844,4823,5843,1744,725,726,5330,5329,728,1241,1755,1242,3807,5854,1756,5853,5836,4815,5835,1736,717,718,5322,5321,3270,1729,1223,4288,3269,1730,3780,3779,3818,3817,2285,2286,1259,4840,1260,1775,736,1249,1763,1250,3815,5862,1764,5861,3826,3825,2293,2294,1267,4848,1268,1783,3322,1789,763,764,3321,1790,5880,2815,640,1153,1667,1154,3719,5766,1668,5765,3738,3737,2205,2206,1179,4760,1180,1695,4796,1213,5311,1214,4795,5818,2232,5817,3746,3745,2213,2214,1187,4768,1188,1703,1160,4239,137,4750,2187,2188,138,4749,1168,4247,145,4758,2195,2196,146,4757,3254,1713,1207,4272,3253,1714,3764,3763,3246,1705,1199,4264,3245,1706,3756,3755,3558,2017,1511,4576,3557,2018,4068,4067,3550,2009,1503,4568,3549,2010,4060,4059,1000,1513,2027,1514,4079,6126,2028,6125,4566,983,4565,3540,3025,4048,3026,3539,4094,4093,2553,2554,511,4604,3576,4603,4034,4033,2501,2502,1475,5056,1476,1991,1008,1521,2035,1522,4087,6134,2036,6133,4558,975,4557,3532,3017,4040,3018,3531,5556,5555,437,5042,6071,2992,438,5041,5548,5547,429,5034,6063,2984,430,5033,3466,1933,907,908,3465,1934,6024,2959,3474,1941,915,916,3473,1942,6032,2967,952,1465,1979,1466,4031,6078,1980,6077,6052,5031,6051,1952,933,934,5538,5537,4996,1413,5511,1414,4995,6018,2432,6017,6044,5023,6043,1944,925,926,5530,5529,5908,4887,5907,1808,789,790,5394,5393,792,1305,1819,1306,3871,5918,1820,5917,5900,4879,5899,1800,781,782,5386,5385,3334,1793,1287,4352,3333,1794,3844,3843,3882,3881,2349,2350,1323,4904,1324,1839,800,1313,1827,1314,3879,5926,1828,5925,3890,3889,2357,2358,1331,4912,1332,1847,3386,1853,827,828,3385,1854,5944,2879,5492,5491,373,4978,6007,2928,374,4977,5484,5483,365,4970,5999,2920,366,4969,3402,1869,843,844,3401,1870,5960,2895,3410,1877,851,852,3409,1878,5968,2903,888,1401,1915,1402,3967,6014,1916,6013,5988,4967,5987,1888,869,870,5474,5473,4932,1349,5447,1350,4931,5954,2368,5953,5980,4959,5979,1880,861,862,5466,5465,
512,1025,1539,1026,3591,5638,1540,5637,3610,3609,2077,2078,1051,4632,1052,1567,4668,1085,5183,1086,4667,5690,2104,5689,3618,3617,2085,2086,1059,4640,1060,1575,1032,4111,9,4622,2059,2060,10,4621,1040,4119,17,4630,2067,2068,18,4629,3126,1585,1079,4144,3125,1586,3636,3635,3118,1577,1071,4136,3117,1578,3628,3627,4070,4069,2529,2530,487,4580,3552,4579,4606,1023,4605,3580,3065,4088,3066,3579,4062,4061,2521,2522,479,4572,3544,4571,4546,451,4545,5568,3013,452,3014,2503,1512,4591,489,5102,2539,2540,490,5101,1520,4599,497,5110,2547,2548,498,5109,3542,2001,1495,4560,3541,2002,4052,4051,3534,1993,1487,4552,3533,1994,4044,4043,1088,4167,65,4678,2115,2116,66,4677,72,2635,3151,2636,585,586,5198,5197,4186,91,4185,5208,2653,92,2654,2143,80,2643,3159,2644,593,594,5206,5205,5244,5243,125,4730,5759,2680,126,4729,3702,3701,2161,2162,119,4212,3184,4211,4194,99,4193,5216,2661,100,2662,2151,3694,3693,2153,2154,111,4204,3176,4203,6068,5047,6067,1968,949,950,5554,5553,1464,4543,441,5054,2491,2492,442,5053,6060,5039,6059,1960,941,942,5546,5545,5028,1445,5543,1446,5027,6050,2464,6049,3978,3977,2445,2446,1419,5000,1420,1935,5508,5507,389,4994,6023,2944,390,4993,3986,3985,2453,2454,1427,5008,1428,1943,5020,1437,5535,1438,5019,6042,2456,6041,4820,1237,5335,1238,4819,5842,2256,5841,4330,235,4329,5352,2797,236,2798,2287,1240,4319,217,4830,2267,2268,218,4829,1248,4327,225,4838,2275,2276,226,4837,4812,1229,5327,1230,4811,5834,2248,5833,4338,243,4337,5360,2805,244,2806,2295,3782,3781,2241,2242,199,4292,3264,4291,3834,3833,2301,2302,1275,4856,1276,1791,4884,1301,5399,1302,4883,5906,2320,5905,4394,299,4393,5416,2861,300,2862,2351,1304,4383,281,4894,2331,2332,282,4893,1312,4391,289,4902,2339,2340,290,4901,4876,1293,5391,1294,4875,5898,2312,5897,4402,307,4401,5424,2869,308,2870,2359,3846,3845,2305,2306,263,4356,3328,4355,3898,3897,2365,2366,1339,4920,1340,1855,1152,4231,129,4742,2179,2180,130,4741,136,2699,3215,2700,649,650,5262,5261,4250,155,4249,5272,2717,156,2718,2207,144,2707,3223,2708,657,658,5270,5269,5308,5307,189,4794,5823,2744,190,4793,3766,3765,2225,2226,183,4276,3248,4275,4258,163,4257,5280,2725,164,2726,2215,3758,3757,2217,2218,175,4268,3240,4267,6004,4983,6003,1904,885,886,5490,5489,1400,4479,377,4990,2427,2428,378,4989,5996,4975,5995,1896,877,878,5482,5481,4964,1381,5479,1382,4963,5986,2400,5985,3914,3913,2381,2382,1355,4936,1356,1871,5444,5443,325,4930,5959,2880,326,4929,3922,3921,2389,2390,1363,4944,1364,1879,4956,1373,5471,1374,4955,5978,2392,5977,
1024,4103,1,4614,2051,2052,2,4613,8,2571,3087,2572,521,522,5134,5133,4122,27,4121,5144,2589,28,2590,2079,16,2579,3095,2580,529,530,5142,5141,5180,5179,61,4666,5695,2616,62,4665,3638,3637,2097,2098,55,4148,3120,4147,4130,35,4129,5152,2597,36,2598,2087,3630,3629,2089,2090,47,4140,3112,4139,5332,5331,213,4818,5847,2768,214,4817,5324,5323,205,4810,5839,2760,206,4809,3306,1773,747,748,3305,1774,5864,2799,3314,1781,755,756,3313,1782,5872,2807,216,2779,3295,2780,729,730,5342,5341,4294,711,4293,3268,2753,3776,2754,3267,224,2787,3303,2788,737,738,5350,5349,4346,251,4345,5368,2813,252,2814,2303,4582,999,4581,3556,3041,4064,3042,3555,488,3051,3567,3052,1001,1002,5614,5613,3582,2041,1535,4600,3581,2042,4092,4091,496,3059,3575,3060,1009,1010,5622,5621,4574,991,4573,3548,3033,4056,3034,3547,4054,4053,2513,2514,471,4564,3536,4563,3522,1989,963,964,3521,1990,6080,3015,4046,4045,2505,2506,463,4556,3528,4555,5396,5395,277,4882,5911,2832,278,4881,5388,5387,269,4874,5903,2824,270,4873,3370,1837,811,812,3369,1838,5928,2863,3378,1845,819,820,3377,1846,5936,2871,280,2843,3359,2844,793,794,5406,5405,4358,775,4357,3332,2817,3840,2818,3331,288,2851,3367,2852,801,802,5414,5413,4410,315,4409,5432,2877,316,2878,2367,64,2627,3143,2628,577,578,5190,5189,5756,4735,5755,1656,637,638,5242,5241,584,1097,1611,1098,3663,5710,1612,5709,4214,631,4213,3188,2673,3696,2674,3187,3162,1629,603,604,3161,1630,5720,2655,3170,1637,611,612,3169,1638,5728,2663,592,1105,1619,1106,3671,5718,1620,5717,4206,623,4205,3180,2665,3688,2666,3179,128,2691,3207,2692,641,642,5254,5253,5820,4799,5819,1720,701,702,5306,5305,648,1161,1675,1162,3727,5774,1676,5773,4278,695,4277,3252,2737,3760,2738,3251,3226,1693,667,668,3225,1694,5784,2719,3234,1701,675,676,3233,1702,5792,2727,656,1169,1683,1170,3735,5782,1684,5781,4270,687,4269,3244,2729,3752,2730,3243,5044,1461,5559,1462,5043,6066,2480,6065,4490,395,4489,5512,2957,396,2958,2447,440,3003,3519,3004,953,954,5566,5565,6020,4999,6019,1920,901,902,5506,5505,5036,1453,5551,1454,5035,6058,2472,6057,4498,403,4497,5520,2965,404,2966,2455,5540,5539,421,5026,6055,2976,422,5025,5532,5531,413,5018,6047,2968,414,5017,4980,1397,5495,1398,4979,6002,2416,6001,4426,331,4425,5448,2893,332,2894,2383,376,2939,3455,2940,889,890,5502,5501,5956,4935,5955,1856,837,838,5442,5441,4972,1389,5487,1390,4971,5994,2408,5993,4434,339,4433,5456,2901,340,2902,2391,5476,5475,357,4962,5991,2912,358,4961,5468,5467,349,4954,5983,2904,350,4953,
3750,3749,2209,2210,167,4260,3232,4259,4286,703,4285,3260,2745,3768,2746,3259,3742,3741,2201,2202,159,4252,3224,4251,4226,131,4225,5248,2693,132,2694,2183,1192,4271,169,4782,2219,2220,170,4781,1200,4279,177,4790,2227,2228,178,4789,3222,1681,1175,4240,3221,1682,3732,3731,3214,1673,1167,4232,3213,1674,3724,3723,1216,4295,193,4806,2243,2244,194,4805,200,2763,3279,2764,713,714,5326,5325,4314,219,4313,5336,2781,220,2782,2271,208,2771,3287,2772,721,722,5334,5333,5372,5371,253,4858,5887,2808,254,4857,3830,3829,2289,2290,247,4340,3312,4339,4322,227,4321,5344,2789,228,2790,2279,3822,3821,2281,2282,239,4332,3304,4331,3686,3685,2145,2146,103,4196,3168,4195,4222,639,4221,3196,2681,3704,2682,3195,3678,3677,2137,2138,95,4188,3160,4187,4162,67,4161,5184,2629,68,2630,2119,1128,4207,105,4718,2155,2156,106,4717,1136,4215,113,4726,2163,2164,114,4725,3158,1617,1111,4176,3157,1618,3668,3667,3150,1609,1103,4168,3149,1610,3660,3659,4660,1077,5175,1078,4659,5682,2096,5681,4106,11,4105,5128,2573,12,2574,2063,56,2619,3135,2620,569,570,5182,5181,5636,4615,5635,1536,517,518,5122,5121,4652,1069,5167,1070,4651,5674,2088,5673,4114,19,4113,5136,2581,20,2582,2071,5156,5155,37,4642,5671,2592,38,4641,5148,5147,29,4634,5663,2584,30,4633,5460,5459,341,4946,5975,2896,342,4945,5452,5451,333,4938,5967,2888,334,4937,3434,1901,875,876,3433,1902,5992,2927,3442,1909,883,884,3441,1910,6000,2935,344,2907,3423,2908,857,858,5470,5469,4422,839,4421,3396,2881,3904,2882,3395,352,2915,3431,2916,865,866,5478,5477,4474,379,4473,5496,2941,380,2942,2431,1280,4359,257,4870,2307,2308,258,4869,264,2827,3343,2828,777,778,5390,5389,4378,283,4377,5400,2845,284,2846,2335,272,2835,3351,2836,785,786,5398,5397,5436,5435,317,4922,5951,2872,318,4921,3894,3893,2353,2354,311,4404,3376,4403,4386,291,4385,5408,2853,292,2854,2343,3886,3885,2345,2346,303,4396,3368,4395,5524,5523,405,5010,6039,2960,406,5009,5516,5515,397,5002,6031,2952,398,5001,3498,1965,939,940,3497,1966,6056,2991,3506,1973,947,948,3505,1974,6064,2999,408,2971,3487,2972,921,922,5534,5533,4486,903,4485,3460,2945,3968,2946,3459,416,2979,3495,2980,929,930,5542,5541,4538,443,4537,5560,3005,444,3006,2495,5076,1493,5591,1494,5075,6098,2512,6097,4586,491,4585,5608,3053,492,3054,2543,1496,4575,473,5086,2523,2524,474,5085,1504,4583,481,5094,2531,2532,482,5093,5068,1485,5583,1486,5067,6090,2504,6089,4594,499,4593,5616,3061,500,3062,2551,4038,4037,2497,2498,455,4548,3520,4547,4090,4089,2557,2558,1531,5112,1532,2047,
4262,679,4261,3236,2721,3744,2722,3235,168,2731,3247,2732,681,682,5294,5293,3262,1721,1215,4280,3261,1722,3772,3771,176,2739,3255,2740,689,690,5302,5301,4254,671,4253,3228,2713,3736,2714,3227,3734,3733,2193,2194,151,4244,3216,4243,3202,1669,643,644,3201,1670,5760,2695,3726,3725,2185,2186,143,4236,3208,4235,5972,4951,5971,1872,853,854,5458,5457,856,1369,1883,1370,3935,5982,1884,5981,5964,4943,5963,1864,845,846,5450,5449,3398,1857,1351,4416,3397,1858,3908,3907,3946,3945,2413,2414,1387,4968,1388,1903,864,1377,1891,1378,3943,5990,1892,5989,3954,3953,2421,2422,1395,4976,1396,1911,3450,1917,891,892,3449,1918,6008,2943,192,2755,3271,2756,705,706,5318,5317,5884,4863,5883,1784,765,766,5370,5369,712,1225,1739,1226,3791,5838,1740,5837,4342,759,4341,3316,2801,3824,2802,3315,3290,1757,731,732,3289,1758,5848,2783,3298,1765,739,740,3297,1766,5856,2791,720,1233,1747,1234,3799,5846,1748,5845,4334,751,4333,3308,2793,3816,2794,3307,256,2819,3335,2820,769,770,5382,5381,5948,4927,5947,1848,829,830,5434,5433,776,1289,1803,1290,3855,5902,1804,5901,4406,823,4405,3380,2865,3888,2866,3379,3354,1821,795,796,3353,1822,5912,2847,3362,1829,803,804,3361,1830,5920,2855,784,1297,1811,1298,3863,5910,1812,5909,4398,815,4397,3372,2857,3880,2858,3371,4198,615,4197,3172,2657,3680,2658,3171,104,2667,3183,2668,617,618,5230,5229,3198,1657,1151,4216,3197,1658,3708,3707,112,2675,3191,2676,625,626,5238,5237,4190,607,4189,3164,2649,3672,2650,3163,3670,3669,2129,2130,87,4180,3152,4179,3138,1605,579,580,3137,1606,5696,2631,3662,3661,2121,2122,79,4172,3144,4171,6036,5015,6035,1936,917,918,5522,5521,920,1433,1947,1434,3999,6046,1948,6045,6028,5007,6027,1928,909,910,5514,5513,3462,1921,1415,4480,3461,1922,3972,3971,4010,4009,2477,2478,1451,5032,1452,1967,928,1441,1955,1442,4007,6054,1956,6053,4018,4017,2485,2486,1459,5040,1460,1975,3514,1981,955,956,3513,1982,6072,3007,5172,5171,53,4658,5687,2608,54,4657,5164,5163,45,4650,5679,2600,46,4649,3082,1549,523,524,3081,1550,5640,2575,3090,1557,531,532,3089,1558,5648,2583,568,1081,1595,1082,3647,5694,1596,5693,5668,4647,5667,1568,549,550,5154,5153,4612,1029,5127,1030,4611,5634,2048,5633,5660,4639,5659,1560,541,542,5146,5145,5588,5587,469,5074,6103,3024,470,5073,5580,5579,461,5066,6095,3016,462,5065,3562,2029,1003,1004,3561,2030,6120,3055,3570,2037,1011,1012,3569,2038,6128,3063,472,3035,3551,3036,985,986,5598,5597,4550,967,4549,3524,3009,4032,3010,3523,480,3043,3559,3044,993,994,5606,5605,4602,507,4601,5624,3069,508,3070,2559,
3238,1697,1191,4256,3237,1698,3748,3747,3230,1689,1183,4248,3229,1690,3740,3739,680,1193,1707,1194,3759,5806,1708,5805,4246,663,4245,3220,2705,3728,2706,3219,3774,3773,2233,2234,191,4284,3256,4283,3714,3713,2181,2182,1155,4736,1156,1671,688,1201,1715,1202,3767,5814,1716,5813,4238,655,4237,3212,2697,3720,2698,3211,3174,1633,1127,4192,3173,1634,3684,3683,3166,1625,1119,4184,3165,1626,3676,3675,616,1129,1643,1130,3695,5742,1644,5741,4182,599,4181,3156,2641,3664,2642,3155,3710,3709,2169,2170,127,4220,3192,4219,3650,3649,2117,2118,1091,4672,1092,1607,624,1137,1651,1138,3703,5750,1652,5749,4174,591,4173,3148,2633,3656,2634,3147,4948,1365,5463,1366,4947,5970,2384,5969,4458,363,4457,5480,2925,364,2926,2415,1368,4447,345,4958,2395,2396,346,4957,1376,4455,353,4966,2403,2404,354,4965,4940,1357,5455,1358,4939,5962,2376,5961,4466,371,4465,5488,2933,372,2934,2423,3910,3909,2369,2370,327,4420,3392,4419,3962,3961,2429,2430,1403,4984,1404,1919,5012,1429,5527,1430,5011,6034,2448,6033,4522,427,4521,5544,2989,428,2990,2479,1432,4511,409,5022,2459,2460,410,5021,1440,4519,417,5030,2467,2468,418,5029,5004,1421,5519,1422,5003,6026,2440,6025,4530,435,4529,5552,2997,436,2998,2487,3974,3973,2433,2434,391,4484,3456,4483,4026,4025,2493,2494,1467,5048,1468,1983,704,1217,1731,1218,3783,5830,1732,5829,3802,3801,2269,2270,1243,4824,1244,1759,4860,1277,5375,1278,4859,5882,2296,5881,3810,3809,2277,2278,1251,4832,1252,1767,1224,4303,201,4814,2251,2252,202,4813,1232,4311,209,4822,2259,2260,210,4821,3318,1777,1271,4336,3317,1778,3828,3827,3310,1769,1263,4328,3309,1770,3820,3819,5684,4663,5683,1584,565,566,5170,5169,1080,4159,57,4670,2107,2108,58,4669,5676,4655,5675,1576,557,558,5162,5161,4644,1061,5159,1062,4643,5666,2080,5665,3594,3593,2061,2062,1035,4616,1036,1551,5124,5123,5,4610,5639,2560,6,4609,3602,3601,2069,2070,1043,4624,1044,1559,4636,1053,5151,1054,4635,5658,2072,5657,768,1281,1795,1282,3847,5894,1796,5893,3866,3865,2333,2334,1307,4888,1308,1823,4924,1341,5439,1342,4923,5946,2360,5945,3874,3873,2341,2342,1315,4896,1316,1831,1288,4367,265,4878,2315,2316,266,4877,1296,4375,273,4886,2323,2324,274,4885,3382,1841,1335,4400,3381,1842,3892,3891,3374,1833,1327,4392,3373,1834,3884,3883,6100,5079,6099,2000,981,982,5586,5585,984,1497,2011,1498,4063,6110,2012,6109,6092,5071,6091,1992,973,974,5578,5577,3526,1985,1479,4544,3525,1986,4036,4035,4074,4073,2541,2542,1515,5096,1516,2031,992,1505,2019,1506,4071,6118,2020,6117,4082,4081,2549,2550,1523,5104,1524,2039,3578,2045,1019,1020,3577,2046,6136,3071,
5940,4919,5939,1840,821,822,5426,5425,1336,4415,313,4926,2363,2364,314,4925,5932,4911,5931,1832,813,814,5418,5417,4900,1317,5415,1318,4899,5922,2336,5921,3850,3849,2317,2318,1291,4872,1292,1807,5380,5379,261,4866,5895,2816,262,4865,3858,3857,2325,2326,1299,4880,1300,1815,4892,1309,5407,1310,4891,5914,2328,5913,832,1345,1859,1346,3911,5958,1860,5957,3930,3929,2397,2398,1371,4952,1372,1887,4988,1405,5503,1406,4987,6010,2424,6009,3938,3937,2405,2406,1379,4960,1380,1895,1352,4431,329,4942,2379,2380,330,4941,1360,4439,337,4950,2387,2388,338,4949,3446,1905,1399,4464,3445,1906,3956,3955,3438,1897,1391,4456,3437,1898,3948,3947,5108,1525,5623,1526,5107,6130,2544,6129,4554,459,4553,5576,3021,460,3022,2511,504,3067,3583,3068,1017,1018,5630,5629,6084,5063,6083,1984,965,966,5570,5569,5100,1517,5615,1518,5099,6122,2536,6121,4562,467,4561,5584,3029,468,3030,2519,5604,5603,485,5090,6119,3040,486,5089,5596,5595,477,5082,6111,3032,478,5081,896,1409,1923,1410,3975,6022,1924,6021,3994,3993,2461,2462,1435,5016,1436,1951,5052,1469,5567,1470,5051,6074,2488,6073,4002,4001,2469,2470,1443,5024,1444,1959,1416,4495,393,5006,2443,2444,394,5005,1424,4503,401,5014,2451,2452,402,5013,3510,1969,1463,4528,3509,1970,4020,4019,3502,1961,1455,4520,3501,1962,4012,4011,5876,4855,5875,1776,757,758,5362,5361,1272,4351,249,4862,2299,2300,250,4861,5868,4847,5867,1768,749,750,5354,5353,4836,1253,5351,1254,4835,5858,2272,5857,3786,3785,2253,2254,1227,4808,1228,1743,5316,5315,197,4802,5831,2752,198,4801,3794,3793,2261,2262,1235,4816,1236,1751,4828,1245,5343,1246,4827,5850,2264,5849,5300,5299,181,4786,5815,2736,182,4785,5292,5291,173,4778,5807,2728,174,4777,3210,1677,651,652,3209,1678,5768,2703,3218,1685,659,660,3217,1686,5776,2711,696,1209,1723,1210,3775,5822,1724,5821,5796,4775,5795,1696,677,678,5282,5281,4740,1157,5255,1158,4739,5762,2176,5761,5788,4767,5787,1688,669,670,5274,5273,4628,1045,5143,1046,4627,5650,2064,5649,4138,43,4137,5160,2605,44,2606,2095,1048,4127,25,4638,2075,2076,26,4637,1056,4135,33,4646,2083,2084,34,4645,4620,1037,5135,1038,4619,5642,2056,5641,4146,51,4145,5168,2613,52,2614,2103,3590,3589,2049,2050,7,4100,3072,4099,3642,3641,2109,2110,1083,4664,1084,1599,5236,5235,117,4722,5751,2672,118,4721,5228,5227,109,4714,5743,2664,110,4713,3146,1613,587,588,3145,1614,5704,2639,3154,1621,595,596,3153,1622,5712,2647,632,1145,1659,1146,3711,5758,1660,5757,5732,4711,5731,1632,613,614,5218,5217,4676,1093,5191,1094,4675,5698,2112,5697,5724,4703,5723,1624,605,606,5210,5209,
4916,1333,5431,1334,4915,5938,2352,5937,4362,267,4361,5384,2829,268,2830,2319,312,2875,3391,2876,825,826,5438,5437,5892,4871,5891,1792,773,774,5378,5377,4908,1325,5423,1326,4907,5930,2344,5929,4370,275,4369,5392,2837,276,2838,2327,5412,5411,293,4898,5927,2848,294,4897,5404,5403,285,4890,5919,2840,286,4889,4852,1269,5367,1270,4851,5874,2288,5873,4298,203,4297,5320,2765,204,2766,2255,248,2811,3327,2812,761,762,5374,5373,5828,4807,5827,1728,709,710,5314,5313,4844,1261,5359,1262,4843,5866,2280,5865,4306,211,4305,5328,2773,212,2774,2263,5348,5347,229,4834,5863,2784,230,4833,5340,5339,221,4826,5855,2776,222,4825,1344,4423,321,4934,2371,2372,322,4933,328,2891,3407,2892,841,842,5454,5453,4442,347,4441,5464,2909,348,2910,2399,336,2899,3415,2900,849,850,5462,5461,5500,5499,381,4986,6015,2936,382,4985,3958,3957,2417,2418,375,4468,3440,4467,4450,355,4449,5472,2917,356,2918,2407,3950,3949,2409,2410,367,4460,3432,4459,5812,4791,5811,1712,693,694,5298,5297,1208,4287,185,4798,2235,2236,186,4797,5804,4783,5803,1704,685,686,5290,5289,4772,1189,5287,1190,4771,5794,2208,5793,3722,3721,2189,2190,1163,4744,1164,1679,5252,5251,133,4738,5767,2688,134,4737,3730,3729,2197,2198,1171,4752,1172,1687,4764,1181,5279,1182,4763,5786,2200,5785,5620,5619,501,5106,6135,3056,502,5105,5612,5611,493,5098,6127,3048,494,5097,3530,1997,971,972,3529,1998,6088,3023,3538,2005,979,980,3537,2006,6096,3031,1016,1529,2043,1530,4095,6142,2044,6141,6116,5095,6115,2016,997,998,5602,5601,5060,1477,5575,1478,5059,6082,2496,6081,6108,5087,6107,2008,989,990,5594,5593,5140,5139,21,4626,5655,2576,22,4625,5132,5131,13,4618,5647,2568,14,4617,3114,1581,555,556,3113,1582,5672,2607,3122,1589,563,564,3121,1590,5680,2615,24,2587,3103,2588,537,538,5150,5149,4102,519,4101,3076,2561,3584,2562,3075,32,2595,3111,2596,545,546,5158,5157,4154,59,4153,5176,2621,60,2622,2111,1408,4487,385,4998,2435,2436,386,4997,392,2955,3471,2956,905,906,5518,5517,4506,411,4505,5528,2973,412,2974,2463,400,2963,3479,2964,913,914,5526,5525,5564,5563,445,5050,6079,3000,446,5049,4022,4021,2481,2482,439,4532,3504,4531,4514,419,4513,5536,2981,420,2982,2471,4014,4013,2473,2474,431,4524,3496,4523,5748,4727,5747,1648,629,630,5234,5233,1144,4223,121,4734,2171,2172,122,4733,5740,4719,5739,1640,621,622,5226,5225,4708,1125,5223,1126,4707,5730,2144,5729,3658,3657,2125,2126,1099,4680,1100,1615,5188,5187,69,4674,5703,2624,70,4673,3666,3665,2133,2134,1107,4688,1108,1623,4700,1117,5215,1118,4699,5722,2136,5721,
5428,5427,309,4914,5943,2864,310,4913,5420,5419,301,4906,5935,2856,302,4905,3338,1805,779,780,3337,1806,5896,2831,3346,1813,787,788,3345,1814,5904,2839,824,1337,1851,1338,3903,5950,1852,5949,5924,4903,5923,1824,805,806,5410,5409,4868,1285,5383,1286,4867,5890,2304,5889,5916,4895,5915,1816,797,798,5402,5401,6132,5111,6131,2032,1013,1014,5618,5617,1528,4607,505,5118,2555,2556,506,5117,6124,5103,6123,2024,1005,1006,5610,5609,5092,1509,5607,1510,5091,6114,2528,6113,4042,4041,2509,2510,1483,5064,1484,1999,5572,5571,453,5058,6087,3008,454,5057,4050,4049,2517,2518,1491,5072,1492,2007,5084,1501,5599,1502,5083,6106,2520,6105,5364,5363,245,4850,5879,2800,246,4849,5356,5355,237,4842,5871,2792,238,4841,3274,1741,715,716,3273,1742,5832,2767,3282,1749,723,724,3281,1750,5840,2775,760,1273,1787,1274,3839,5886,1788,5885,5860,4839,5859,1760,741,742,5346,5345,4804,1221,5319,1222,4803,5826,2240,5825,5852,4831,5851,1752,733,734,5338,5337,5652,4631,5651,1552,533,534,5138,5137,536,1049,1563,1050,3615,5662,1564,5661,5644,4623,5643,1544,525,526,5130,5129,3078,1537,1031,4096,3077,1538,3588,3587,3626,3625,2093,2094,1067,4648,1068,1583,544,1057,1571,1058,3623,5670,1572,5669,3634,3633,2101,2102,1075,4656,1076,1591,3130,1597,571,572,3129,1598,5688,2623,320,2883,3399,2884,833,834,5446,5445,6012,4991,6011,1912,893,894,5498,5497,840,1353,1867,1354,3919,5966,1868,5965,4470,887,4469,3444,2929,3952,2930,3443,3418,1885,859,860,3417,1886,5976,2911,3426,1893,867,868,3425,1894,5984,2919,848,1361,1875,1362,3927,5974,1876,5973,4462,879,4461,3436,2921,3944,2922,3435,384,2947,3463,2948,897,898,5510,5509,6076,5055,6075,1976,957,958,5562,5561,904,1417,1931,1418,3983,6030,1932,6029,4534,951,4533,3508,2993,4016,2994,3507,3482,1949,923,924,3481,1950,6040,2975,3490,1957,931,932,3489,1958,6048,2983,912,1425,1939,1426,3991,6038,1940,6037,4526,943,4525,3500,2985,4008,2986,3499,4788,1205,5303,1206,4787,5810,2224,5809,4234,139,4233,5256,2701,140,2702,2191,184,2747,3263,2748,697,698,5310,5309,5764,4743,5763,1664,645,646,5250,5249,4780,1197,5295,1198,4779,5802,2216,5801,4242,147,4241,5264,2709,148,2710,2199,5284,5283,165,4770,5799,2720,166,4769,5276,5275,157,4762,5791,2712,158,4761,4724,1141,5239,1142,4723,5746,2160,5745,4170,75,4169,5192,2637,76,2638,2127,120,2683,3199,2684,633,634,5246,5245,5700,4679,5699,1600,581,582,5186,5185,4716,1133,5231,1134,4715,5738,2152,5737,4178,83,4177,5200,2645,84,2646,2135,5220,5219,101,4706,5735,2656,102,4705,5212,5211,93,4698,5727,2648,94,4697,
4006,4005,2465,2466,423,4516,3488,4515,4542,959,4541,3516,3001,4024,3002,3515,3998,3997,2457,2458,415,4508,3480,4507,4482,387,4481,5504,2949,388,2950,2439,1448,4527,425,5038,2475,2476,426,5037,1456,4535,433,5046,2483,2484,434,5045,3478,1937,1431,4496,3477,1938,3988,3987,3470,1929,1423,4488,3469,1930,3980,3979,448,3011,3527,3012,961,962,5574,5573,6140,5119,6139,2040,1021,1022,5626,5625,968,1481,1995,1482,4047,6094,1996,6093,4598,1015,4597,3572,3057,4080,3058,3571,3546,2013,987,988,3545,2014,6104,3039,3554,2021,995,996,3553,2022,6112,3047,976,1489,2003,1490,4055,6102,2004,6101,4590,1007,4589,3564,3049,4072,3050,3563,3942,3941,2401,2402,359,4452,3424,4451,4478,895,4477,3452,2937,3960,2938,3451,3934,3933,2393,2394,351,4444,3416,4443,4418,323,4417,5440,2885,324,2886,2375,1384,4463,361,4974,2411,2412,362,4973,1392,4471,369,4982,2419,2420,370,4981,3414,1873,1367,4432,3413,1874,3924,3923,3406,1865,1359,4424,3405,1866,3916,3915,4390,807,4389,3364,2849,3872,2850,3363,296,2859,3375,2860,809,810,5422,5421,3390,1849,1343,4408,3389,1850,3900,3899,304,2867,3383,2868,817,818,5430,5429,4382,799,4381,3356,2841,3864,2842,3355,3862,3861,2321,2322,279,4372,3344,4371,3330,1797,771,772,3329,1798,5888,2823,3854,3853,2313,2314,271,4364,3336,4363,5204,5203,85,4690,5719,2640,86,4689,5196,5195,77,4682,5711,2632,78,4681,3178,1645,619,620,3177,1646,5736,2671,3186,1653,627,628,3185,1654,5744,2679,88,2651,3167,2652,601,602,5214,5213,4166,583,4165,3140,2625,3648,2626,3139,96,2659,3175,2660,609,610,5222,5221,4218,123,4217,5240,2685,124,2686,2175,3110,1569,1063,4128,3109,1570,3620,3619,3102,1561,1055,4120,3101,1562,3612,3611,552,1065,1579,1066,3631,5678,1580,5677,4118,535,4117,3092,2577,3600,2578,3091,3646,3645,2105,2106,63,4156,3128,4155,3586,3585,2053,2054,1027,4608,1028,1543,560,1073,1587,1074,3639,5686,1588,5685,4110,527,4109,3084,2569,3592,2570,3083,5268,5267,149,4754,5783,2704,150,4753,5260,5259,141,4746,5775,2696,142,4745,3242,1709,683,684,3241,1710,5800,2735,3250,1717,691,692,3249,1718,5808,2743,152,2715,3231,2716,665,666,5278,5277,4230,647,4229,3204,2689,3712,2690,3203,160,2723,3239,2724,673,674,5286,5285,4282,187,4281,5304,2749,188,2750,2239,4326,743,4325,3300,2785,3808,2786,3299,232,2795,3311,2796,745,746,5358,5357,3326,1785,1279,4344,3325,1786,3836,3835,240,2803,3319,2804,753,754,5366,5365,4318,735,4317,3292,2777,3800,2778,3291,3798,3797,2257,2258,215,4308,3280,4307,3266,1733,707,708,3265,1734,5824,2759,3790,3789,2249,2250,207,4300,3272,4299,
4518,935,4517,3492,2977,4000,2978,3491,424,2987,3503,2988,937,938,5550,5549,3518,1977,1471,4536,3517,1978,4028,4027,432,2995,3511,2996,945,946,5558,5557,4510,927,4509,3484,2969,3992,2970,3483,3990,3989,2449,2450,407,4500,3472,4499,3458,1925,899,900,3457,1926,6016,2951,3982,3981,2441,2442,399,4492,3464,4491,5716,4695,5715,1616,597,598,5202,5201,600,1113,1627,1114,3679,5726,1628,5725,5708,4687,5707,1608,589,590,5194,5193,3142,1601,1095,4160,3141,1602,3652,3651,3690,3689,2157,2158,1131,4712,1132,1647,608,1121,1635,1122,3687,5734,1636,5733,3698,3697,2165,2166,1139,4720,1140,1655,3194,1661,635,636,3193,1662,5752,2687,960,1473,1987,1474,4039,6086,1988,6085,4058,4057,2525,2526,1499,5080,1500,2015,5116,1533,5631,1534,5115,6138,2552,6137,4066,4065,2533,2534,1507,5088,1508,2023,1480,4559,457,5070,2507,2508,458,5069,1488,4567,465,5078,2515,2516,466,5077,3574,2033,1527,4592,3573,2034,4084,4083,3566,2025,1519,4584,3565,2026,4076,4075,3622,3621,2081,2082,39,4132,3104,4131,4158,575,4157,3132,2617,3640,2618,3131,3614,3613,2073,2074,31,4124,3096,4123,4098,3,4097,5120,2565,4,2566,2055,1064,4143,41,4654,2091,2092,42,4653,1072,4151,49,4662,2099,2100,50,4661,3094,1553,1047,4112,3093,1554,3604,3603,3086,1545,1039,4104,3085,1546,3596,3595,4454,871,4453,3428,2913,3936,2914,3427,360,2923,3439,2924,873,874,5486,5485,3454,1913,1407,4472,3453,1914,3964,3963,368,2931,3447,2932,881,882,5494,5493,4446,863,4445,3420,2905,3928,2906,3419,3926,3925,2385,2386,343,4436,3408,4435,3394,1861,835,836,3393,1862,5952,2887,3918,3917,2377,2378,335,4428,3400,4427,5780,4759,5779,1680,661,662,5266,5265,664,1177,1691,1178,3743,5790,1692,5789,5772,4751,5771,1672,653,654,5258,5257,3206,1665,1159,4224,3205,1666,3716,3715,3754,3753,2221,2222,1195,4776,1196,1711,672,1185,1699,1186,3751,5798,1700,5797,3762,3761,2229,2230,1203,4784,1204,1719,3258,1725,699,700,3257,1726,5816,2751,3366,1825,1319,4384,3365,1826,3876,3875,3358,1817,1311,4376,3357,1818,3868,3867,808,1321,1835,1322,3887,5934,1836,5933,4374,791,4373,3348,2833,3856,2834,3347,3902,3901,2361,2362,319,4412,3384,4411,3842,3841,2309,2310,1283,4864,1284,1799,816,1329,1843,1330,3895,5942,1844,5941,4366,783,4365,3340,2825,3848,2826,3339,3302,1761,1255,4320,3301,1762,3812,3811,3294,1753,1247,4312,3293,1754,3804,3803,744,1257,1771,1258,3823,5870,1772,5869,4310,727,4309,3284,2769,3792,2770,3283,3838,3837,2297,2298,255,4348,3320,4347,3778,3777,2245,2246,1219,4800,1220,1735,752,1265,1779,1266,3831,5878,1780,5877,4302,719,4301,3276,2761,3784,2762,3275,
3494,1953,1447,4512,3493,1954,4004,4003,3486,1945,1439,4504,3485,1946,3996,3995,936,1449,1963,1450,4015,6062,1964,6061,4502,919,4501,3476,2961,3984,2962,3475,4030,4029,2489,2490,447,4540,3512,4539,3970,3969,2437,2438,1411,4992,1412,1927,944,1457,1971,1458,4023,6070,1972,6069,4494,911,4493,3468,2953,3976,2954,3467,3430,1889,1383,4448,3429,1890,3940,3939,3422,1881,1375,4440,3421,1882,3932,3931,872,1385,1899,1386,3951,5998,1900,5997,4438,855,4437,3412,2897,3920,2898,3411,3966,3965,2425,2426,383,4476,3448,4475,3906,3905,2373,2374,1347,4928,1348,1863,880,1393,1907,1394,3959,6006,1908,6005,4430,847,4429,3404,2889,3912,2890,3403,4692,1109,5207,1110,4691,5714,2128,5713,4202,107,4201,5224,2669,108,2670,2159,1112,4191,89,4702,2139,2140,90,4701,1120,4199,97,4710,2147,2148,98,4709,4684,1101,5199,1102,4683,5706,2120,5705,4210,115,4209,5232,2677,116,2678,2167,3654,3653,2113,2114,71,4164,3136,4163,3706,3705,2173,2174,1147,4728,1148,1663,4756,1173,5271,1174,4755,5778,2192,5777,4266,171,4265,5288,2733,172,2734,2223,1176,4255,153,4766,2203,2204,154,4765,1184,4263,161,4774,2211,2212,162,4773,4748,1165,5263,1166,4747,5770,2184,5769,4274,179,4273,5296,2741,180,2742,2231,3718,3717,2177,2178,135,4228,3200,4227,3770,3769,2237,2238,1211,4792,1212,1727,1472,4551,449,5062,2499,2500,450,5061,456,3019,3535,3020,969,970,5582,5581,4570,475,4569,5592,3037,476,3038,2527,464,3027,3543,3028,977,978,5590,5589,5628,5627,509,5114,6143,3064,510,5113,4086,4085,2545,2546,503,4596,3568,4595,4578,483,4577,5600,3045,484,3046,2535,4078,4077,2537,2538,495,4588,3560,4587,3878,3877,2337,2338,295,4388,3360,4387,4414,831,4413,3388,2873,3896,2874,3387,3870,3869,2329,2330,287,4380,3352,4379,4354,259,4353,5376,2821,260,2822,2311,1320,4399,297,4910,2347,2348,298,4909,1328,4407,305,4918,2355,2356,306,4917,3350,1809,1303,4368,3349,1810,3860,3859,3342,1801,1295,4360,3341,1802,3852,3851,4134,551,4133,3108,2593,3616,2594,3107,40,2603,3119,2604,553,554,5166,5165,3134,1593,1087,4152,3133,1594,3644,3643,48,2611,3127,2612,561,562,5174,5173,4126,543,4125,3100,2585,3608,2586,3099,3606,3605,2065,2066,23,4116,3088,4115,3074,1541,515,516,3073,1542,5632,2567,3598,3597,2057,2058,15,4108,3080,4107,3814,3813,2273,2274,231,4324,3296,4323,4350,767,4349,3324,2809,3832,2810,3323,3806,3805,2265,2266,223,4316,3288,4315,4290,195,4289,5312,2757,196,2758,2247,1256,4335,233,4846,2283,2284,234,4845,1264,4343,241,4854,2291,2292,242,4853,3286,1745,1239,4304,3285,1746,3796,3795,3278,1737,1231,4296,3277,1738,3788,3787
  };

  static const double hxtDeclareAligned defaultShift[3] = {0.5,0.5,0.5};

  if(mid01==NULL)
    mid01=defaultShift;

  const uint32_t nmax = 0x200000; // 1<<21

  double hxtDeclareAligned32 middle[4];
  double hxtDeclareAligned32 f0[4];
  double hxtDeclareAligned32 f1[4];
  double hxtDeclareAligned32 sub1[4];

  double widthMax = 0.0;
  for(int i=0; i<3; i++) {
    double width = bbox->max[i] - bbox->min[i];
    if(width > widthMax)
      widthMax = width;
  }

  for(int i=0; i<3; i++) {
    double xmin;
    double xmax;
    if(widthMax > 1.5*(bbox->max[i] - bbox->min[i])) { // we want the bbox to stay relatively cubic
      if(mid01[i]>=0.5) {
        xmin = bbox->min[i];
        xmax = bbox->min[i] + widthMax;
      }
      else {
        xmax = bbox->max[i];
        xmin = bbox->max[i] - widthMax;
      }
    }
    else {
      xmin = bbox->min[i];
      xmax = bbox->max[i];
    }

    middle[i] = mid01[i] * (xmax - xmin) + xmin;
    f0[i] = (nmax/2) / (middle[i] - xmin);
    f1[i] = (nmax/2) / (xmax - middle[i]);
    sub1[i] = 2*middle[i] - xmax;
    while((uint32_t) ((xmax - sub1[i]) * f1[i]) >= nmax){
      f1[i] = nextbeforef(f1[i]);
    }
  }

  #pragma omp parallel
  {
    #pragma omp for schedule(static)
    for (uint32_t i=0; i<n/32; i++)
    {
      uint64_t hxtDeclareAligned zorder[32];

      #pragma omp simd
      for (int j=0; j<32; j++) {
        uint32_t xyz[3];
        for(int k=0; k<3; k++) {
          double v = vertices[32*i+j].coord[k];
          if(v < middle[k])
            xyz[k] = (v - bbox->min[k]) *f0[k];
          else
            xyz[k] = (v - sub1[k]) *f1[k];
        }

        zorder[j] = Zorder(xyz);
      }

      uint64_t hxtDeclareAligned transform[32];
      uint64_t hxtDeclareAligned out[32];

      #pragma omp simd
      for (int j=0; j<32; j++)
        transform[j] = zorder[j]>>54;

      for (int j=0; j<8; j++){
        transform[4*j+0] = moore_hilbert2[transform[4*j+0]];
        transform[4*j+1] = moore_hilbert2[transform[4*j+1]];
        transform[4*j+2] = moore_hilbert2[transform[4*j+2]];
        transform[4*j+3] = moore_hilbert2[transform[4*j+3]];
      }

      #pragma omp simd
      for (int j=0; j<32; j++)
        out[j] = transform[j] & 0x1FF;

      for (int iter=45; iter>=0; iter-=9) {
        #pragma omp simd
        for (int j=0; j<32; j++)
          transform[j] = (transform[j] & ~0x1FF) | (zorder[j]>>iter & 0x1FF);

        for (int j=0; j<8; j++){
          transform[4*j+0] = hilbert3[transform[4*j+0]];
          transform[4*j+1] = hilbert3[transform[4*j+1]];
          transform[4*j+2] = hilbert3[transform[4*j+2]];
          transform[4*j+3] = hilbert3[transform[4*j+3]];
        }

        #pragma omp simd
        for (int j=0; j<32; j++)
          out[j] = (out[j] << 9) | (transform[j] & 0x1FF);
      }
      
      for (int j=0; j<8; j++) {
        vertices[32*i+4*j+0].padding.hilbertDist = out[4*j+0];
        vertices[32*i+4*j+1].padding.hilbertDist = out[4*j+1];
        vertices[32*i+4*j+2].padding.hilbertDist = out[4*j+2];
        vertices[32*i+4*j+3].padding.hilbertDist = out[4*j+3];
      }
    }

    #pragma omp for
    for (uint32_t i=n/32*32; i<n; i++) {
      uint64_t zorder;
      {
        uint32_t xyz[3];
        for(int k=0; k<3; k++) {
          double v = vertices[i].coord[k];
          if(v < middle[k])
            xyz[k] = (v - bbox->min[k]) *f0[k];
          else
            xyz[k] = (v - sub1[k]) *f1[k];
        }

        xyz[2]/=4;

        zorder = Zorder(xyz);
      }

      uint16_t transform;
      uint64_t out;

      transform = zorder>>54;
      transform = moore_hilbert2[transform];
      out = transform & 0x1FF;

      for (int iter=45; iter>=0; iter-=9) {
        transform = (transform & ~0x1FF) | (zorder>>iter & 0x1FF);
        transform = hilbert3[transform];
        out = (out << 9) | (transform & 0x1FF);
      }
          
      vertices[i].padding.hilbertDist = out;
    }
  }

  return HXT_STATUS_OK;
}


static inline uint64_t getVertexDist64(HXTVertex* const __restrict__  v, const void* userData)
{
  HXT_UNUSED(userData);
  return v->padding.hilbertDist;
}

HXTStatus hxtVerticesSort(HXTVertex* const __restrict__  vertices, const uint32_t n)
{
  HXT_ASSERT(vertices!=NULL);

  HXTSORT64_UNIFORM(HXTVertex, vertices, n, ((UINT64_C(1)<<63)-1), getVertexDist64, NULL);
  return HXT_STATUS_OK;
}

static inline uint64_t getNodeInfoDist64(HXTNodeInfo*  const __restrict__ nodeInfo, const void* userData)
{
  HXT_UNUSED(userData);
  return nodeInfo->hilbertDist;
}

HXTStatus hxtNodeInfoSort(HXTNodeInfo*  const __restrict__ array, const uint32_t n)
{
  HXT_ASSERT(array!=NULL);
  if(sizeof(HXTNodeInfo)==sizeof(HXTGroup2)){
  	HXT_CHECK( group2_sort_v0((HXTGroup2*) array, n, ((UINT64_C(1)<<63)-1)) );
  }
  else {
  	// actually, this is always optimized away...
	HXTSORT64_UNIFORM(HXTNodeInfo, array, n, ((UINT64_C(1)<<63)-1), getNodeInfoDist64, NULL);
  }
  return HXT_STATUS_OK;
}


/*********************************** shuffle functions ***********************************************/
static inline uint32_t getVertexDist32(HXTVertex* const __restrict__  v, const void* userData)
{
  HXT_UNUSED(userData);
  return v->padding.hilbertDist;
}

static inline uint32_t getNodeInfoDist32(HXTNodeInfo*  const __restrict__ nodeInfo, const void* userData)
{
  HXT_UNUSED(userData);
  return nodeInfo->hilbertDist;
}

/* for the non-static function, use a 22 bit key and a sort with two pass so we don't need to copy */
HXTStatus hxtVerticesShuffle(HXTVertex* const __restrict__ vertices, const uint32_t n){
  #pragma omp parallel for simd
  for (uint32_t i=0; i<n; i++){
    vertices[i].padding.hilbertDist = hash32(i);
  }

  HXTSORT32_UNIFORM(HXTVertex, vertices, n, UINT32_MAX, getVertexDist32, NULL);
  return HXT_STATUS_OK;
}

/* for the non-static function, use a 22 bit key and a sort with two pass so we don't need to copy */
HXTStatus hxtNodeInfoShuffle(HXTNodeInfo* const __restrict__ nodeInfo, const uint32_t n){
  #pragma omp parallel for simd
  for (uint32_t i=0; i<n; i++){
    nodeInfo[i].hilbertDist = hash32(i);
  }

  HXTSORT32_UNIFORM(HXTNodeInfo, nodeInfo, n, UINT32_MAX, getNodeInfoDist32, NULL);
  return HXT_STATUS_OK;
}
